home *** CD-ROM | disk | FTP | other *** search
/ Amiga Developer CD 2.1 / Amiga Developer CD v2.1.iso / Extras / IFF / IFF_Forms / ILBM.PCHG.doc < prev    next >
Encoding:
Text File  |  1993-03-01  |  14.3 KB  |  373 lines
  1. Line by line palette control information (Sebastiano Vigna)
  2.  
  3.                                     PCHG
  4.  
  5.           A proposal for a new line-by-line palette control format
  6.  
  7.                             by Sebastiano Vigna
  8.  
  9.                         *** Preliminary version ***
  10.  
  11.                       $VER: PCHG specs 0.6 (28.11.91)
  12.  
  13.  
  14.  
  15. After struggling a lot with CTBL, SHAM, and whatever else was invented for
  16. specifying palette changes at every scan line in order to implement them in
  17. Mostra (my ILBM viewer), I decided there was no way to make them really
  18. work. Each program uses them in a different way, with different
  19. non-documented specifications. SHAM is hardwired to 200 lines, and the color
  20. of the last pixels of a screen depends on the horizontal position of the
  21. screen itself because of a wrong computation of the free Copper DMA slots.
  22. CTBL is theoretically undisplayable without freezing everything and yet all
  23. images I ever saw changed much less than 15 colors per scan line, which you
  24. can perfectly do with the Copper (thanks to ASDG's DDHR utility for this
  25. info). There is moveover a great confusion about the role of the CMAP chunk
  26. with respect to all those guys.
  27.  
  28. Yet the technology is very simple. Just change some color register each scan
  29. line. Very Amiga specific, but it works, and it works really well.
  30.  
  31. This document describes the PCHG (Palette Changes) chunk, an ILBM property
  32. chunk for controlling efficiently and reasonably the palette changes at each
  33. scan line. Also, I included technical info and code about the current
  34. allowable per line palette changes.
  35.  
  36. This proposal is a team work. It was lively discussed with many other
  37. people, including Joanne Dow, Andy Finkel, J. Edward Hanway, Charles Heath,
  38. David Joiner, Jim Kent, Ilya Shubentsov, Mike Sinz, Loren Wilton. There is
  39. certainly some other people I'm forgetting to mention though.
  40.  
  41. What's good in what follows was suggested by them. I'm responsable for any
  42. error, omission, bad English and bad design.
  43.  
  44.  
  45.  
  46.                                 Design goals
  47.  
  48. - Being able to specify *only* the changes which are really required.
  49.  
  50. - Being able to specify 24-bit precision color changes, and an alpha channel.
  51.  
  52. - Specifying correctly the relation PCHG<->CMAP.
  53.  
  54. - Getting a chunk which is usually smaller than SHAM or CTBL.
  55.  
  56. - Having a policy about Copper-only displayability.
  57.  
  58. - Being able to change 65536 registers.
  59.  
  60. - Specifying two storage formats: a very dense 4-bit 32 register format for
  61. current technology, and an open-ended, 24-bit+alpha channel, 65536 registers
  62. format with compression for all future uses.
  63.  
  64. - Distributing public domain code for PCHG compression/decompression and
  65. Copperlist building.
  66.  
  67.  
  68.  
  69.                             Informal description
  70.  
  71. PCHG starts with the following header:
  72.  
  73. struct PCHGHeader {
  74.    UWORD Compression;
  75.    UWORD Flags;
  76.    WORD  StartLine;
  77.    UWORD LineCount;
  78.    UWORD MinReg;
  79.    UWORD MaxReg;
  80.    UWORD TreeSize;
  81.    UWORD Reserved;
  82.    ULONG OriginalSize;
  83. };
  84.  
  85. The only Compression values currently defined are PCHG_COMP_NONE and
  86. PCHG_COMP_HUFFMANN. The Flags field has three bits currently defined,
  87. PCHGF_4BIT, PCHGF_32BIT, PCHGF_USE_ALPHA. The StartLine and LineCount fields
  88. specify the range controlled by the line mask, as we will see later. The
  89. MinReg and MaxReg fields tells you the minimum and the maximum register
  90. changed in the chunk. Their purpose is to allow optimization (such as
  91. grouping of the modified registers in some special bank). OriginalSize
  92. contains the size of the rest of the chunk when it will be decompressed (if
  93. no compression is selected, OriginalSize should anyway be set to the size of
  94. the rest of the chunk, i.e., ChunkSize-sizeof(struct PCHGHeader)).
  95.  
  96. If Compression is PCHG_COMP_HUFFMANN, the rest of the chunk is compressed.
  97. The first TreeSize bytes contain the decompression tree, and then the
  98. compressed chunk (originally OriginalSize bytes long) follows. See the
  99. section Compression for information about the format used by PCHG.
  100.  
  101. First of all, there is a array of (LineCount+31)/32 longwords (that is, a
  102. bit mask of LineCount bits rounded up to the nearest longword). Each bit in
  103. the mask tells you if there are palette changes in the corresponding line.
  104. Bit 0 corresponds to line StartLine, bit 1 to line StartLine+1 and so on.
  105. Note that StartLine is a (possibly negative) offset from the top of the
  106. screen.
  107.  
  108. The information about the palette changes is stored immediately after the
  109. bit mask. For each bit set to 1 in the mask there is a variable length
  110. structure. These structures are recorded contiguously, and they are
  111. different depending on the PCHGF_4BIT or the PCHGF_32BIT flags being set. In
  112. the first case, we use
  113.  
  114. struct SmallLineChanges {
  115.    UBYTE ChangeCount16;
  116.    UBYTE ChangeCount32;
  117.    UWORD PaletteChange[];
  118. };
  119.  
  120. The PaletteChange array contains ChangeCount16+ChangeCount32 elements. For
  121. each element, the lower 12 bits specify a color in 4-bit RGB form, while
  122. the upper 4 bits specify the register number. More precisely, for the
  123. first ChangeCount16 elements you take as register number the upper
  124. 4 bits, and for the following ChangeCount32 elements you take as register
  125. number the upper 4 bits+16. Thus, you can address a 32 register palette.
  126.  
  127. In the second case, we use
  128.  
  129. struct BigLineChanges {
  130.    UWORD ChangeCount;
  131.    struct BigPaletteChange PaletteChange[];
  132. };
  133.  
  134. where
  135.  
  136. struct BigPaletteChange {
  137.    UWORD Register;
  138.    UBYTE Alpha, Red, Blue, Green;
  139. };
  140.  
  141. The array PaletteChange contains ChangeCount elements. For each elements,
  142. Register specify the register number, while the Alpha, Red, Blue, Green
  143. values specify the 8-bit content of the respective channels. Alpha should
  144. be used only if the PCHGF_USE_ALPHA flag is set in the header.
  145.  
  146.  
  147. CMAP and PCHG don't interfere. It's up to the intelligence of the IFF ILBM
  148. writer using CMAP for the first line color register values, and then
  149. specifying the changes from line 1 (2 for laced pictures) onwards using
  150. PCHG. CMAP has to be loaded, as specified by the IFF ILBM specs.
  151.  
  152. Note that PCHG is mainly a time saver chunk. The ``right thing'' for a
  153. program should be generating at run-time the palette changes when a picture
  154. with more colors than available on the hardware has to be shown. However,
  155. the current computational power make this goal unrealistic. PCHG allows to
  156. display in a very short time images with lot of colors on the current Amiga
  157. hardware. It can be also used to write down a custom Copper list (maybe
  158. changing only the background color register) together with an image.
  159.  
  160. Some politeness is required from the PCHG writer. PCHG allows you to specify
  161. as many as 65535 per line color changes, which are a little bit unrealistic
  162. on the current hardware. Programs should never save with a picture more
  163. changes than available by using Copper lists only. This issue is thouroughly
  164. explained in the ``Writing changes'' section.
  165.  
  166. This kind of politeness is enforced by the specification. I have yet to see
  167. people which is interested in freezing their machine just in order to view a
  168. picture. DMA contention is a thing, lockup is another. PCHG chunks which do
  169. not conform to the rules explained below are to be considered syntactically
  170. incorrect. If you want specify more changes that available through the
  171. system Copper calls CWAIT/CMOVE, please use another chunk and don't mess up
  172. the PCHG interpretation.
  173.  
  174.  
  175.  
  176.                                 Compression
  177.  
  178.  
  179. (Caveat: you don't need to read this if you're not really interested because
  180. there are ready-to-use C functions for compression and decompression;
  181. moreover, 4-bit PCHG chunks are usually so entropic that the size gain is
  182. less than the size of the tree, so you shouldn't compress them.)
  183.  
  184. PCHG uses a classical static Huffmann encoding for the line mask and the
  185. LineChanges array. The coding tree is recorded just before the compressed
  186. data in a form which takes 1022 bytes or less (usually ~700). Its (byte)
  187. length is stored in the TreeSize field of the PCHGHeader structure.
  188. Moreover, this form is ready for a fast and short decompression
  189. algorithm---no preprocessing is needed. For references about the Huffmann
  190. encoding, see Sedgewick's ``Algorithms in C''. Note that the number of
  191. compressed data bits stored is rounded up to a multiple of 32 (the
  192. decompression routine knows the original length of the data, so the
  193. exceeding bits won't be parsed).
  194.  
  195. The format of the tree is recursive. We start to code from the end of a 511
  196. WORD array, and we work backwards. To code an internal node at the position
  197. WORD *Pos, the left subtree is recorded at Pos-1 with a code of length t,
  198. and the left subtree is coded at Pos-1-t. Then an offset (-t-1)*2 is stored
  199. in Pos, and the length of the resulting coding is 1+t+length of the left
  200. subtree code. An external node is coded as the character associated with the
  201. eighth bit set. As a final optimization, if the left subtree to code is an
  202. external node, we just store the character associated in the place of the
  203. negative offset
  204.  
  205. For instance, the tree
  206.  
  207.                                 /\
  208.                                /  \
  209.                               a    b
  210.  
  211. is coded as the word array [ a | 0x100 ] [ b ]. Note that without the eighth
  212. bit trick, it would be impossible to store this tree, since it would be
  213. confused with the tree formed by the external node b only.
  214.  
  215. Another simple example:
  216.  
  217.                                  /\
  218.                                 /  \
  219.                                /    \
  220.                               /\    /\
  221.                              /  \  /  \
  222.                             a   b  c  /\
  223.                                      /  \
  224.                                     d    e
  225.  
  226.  
  227. is coded as
  228.  
  229.     [ d | 0x100 ] [ e ] [ c | 0x100 ] [ -4 ] [ a | 0x100 ] [ b ] [ -6 ].
  230.  
  231. Decompression is very easy. We start from the end of the tree code.
  232.  
  233. If we pick a 0 bit in the packed data, we move a word to the left and fetch
  234. the current word. If it's positive and with the 8th bit set the tree is
  235. finished and we store to the destination the lower byte of the word we
  236. fetched, otherwise we pick another bit.
  237.  
  238. If we pick a 1 bit, we fetch the current word. If it's positive, we store
  239. it. Otherwise we add it to the current position and we pick another bit.
  240. (Here you can see the reason why the offset is not stored as a word offset,
  241. but rather as a byte offset. We avoid a conversion word->byte offset for
  242. each bit set to 1 of the source).
  243.  
  244.  
  245.  
  246.  
  247.                               Writing changes
  248.  
  249. PCHG is a machine-independent format. Nonetheless, it's been developed
  250. mainly for supporting the Amiga Copperlist palette changes. Thus, it's not a
  251. surprise to find included with the format definition a policy about the
  252. amount of color changes which you should write.
  253.  
  254. Under the current Amiga hardware and system software, you should never
  255. generate more than 7 (seven) changes per line. Moreover, in laced pictures
  256. the changes can only happen on even lines. Thus, for a 400 lines laced
  257. picture you have 200*7=1400 color changes at lines 0, 2, 4, etc., while for
  258. a 256 lines non laced picture you have 256*7= 1792 color changes at lines 0,
  259. 1, 2, etc. Of course you can save less changes, or no changes at all on some
  260. lines.
  261.  
  262. The point here is that you shouldn't save more changes than that. If you
  263. want to write a picture with more changes, or changes on odd laced lines,
  264. please make aware the user of the fact that probably most viewer supporting
  265. PCHG won't be able to display it. The Amiga community has been already
  266. bitten by the problems of SHAM and CTBL, and we have neither need nor will
  267. of repeating the experience.
  268.  
  269. Of course, when faster, better Amiga chips will be around, this magic number
  270. will change. But for the time being, this is the system limitation.
  271.  
  272. If you have a technical background about the Copper, that's why:
  273.  
  274. The Copper y register has 8-bits resolution. When it arrives at the 255th
  275. video line, it wraps up to 0. Thus, the system places a WAIT(226,255) Copper
  276. instruction in order to stop correctly the video display on PAL screens.
  277.  
  278. If you want more than 7 changes, you have to start poking the color
  279. registers with the Copper just after a video line is finished (as SHAM). But
  280. on the 255th video line, MrgCop() will merge your user Copperlist with the
  281. system one in such a way that the WAIT(226,255) will happen *after* the
  282. counter wrapped, so the Copper will be locked until the next vertical blank.
  283. As a result, the following color changes won't be executed, and some trash
  284. will be displayed at the bottom of the screen (this indeed happens with
  285. SHAM).
  286.  
  287. In order to avoid this, it is necessary to use only WAIT(0,<line>)
  288. instructions. The time available before the display data fetch start allows
  289. only 7 color changes, and wide range experiments confirmed this.
  290.  
  291. Finally, due to a limitation of MrgCop(), it's not possible specifying WAITs
  292. on odd interlaced lines.
  293.  
  294.  
  295.  
  296.  
  297.                             The transition phase
  298.  
  299.  
  300. This specification is distributed with a complete set of C functions which
  301. take care of compression, decompression and Copperlist building. Adding
  302. support for PCHG in your programs should be pretty straightforward.
  303.  
  304.  
  305.  
  306.  
  307.                             Formal specification
  308.  
  309. struct PCHGHeader {
  310.    UWORD Compression;
  311.    UWORD Flags;
  312.    WORD  StartLine;
  313.    UWORD LineCount;
  314.    UWORD MinReg;
  315.    UWORD MaxReg;
  316.    UWORD TreeSize;
  317.    UWORD Reserved;
  318.    ULONG OriginalSize;
  319. };
  320.  
  321. struct SmallLineChanges {
  322.    UBYTE ChangeCount16;
  323.    UBYTE ChangeCount32;
  324.    UWORD PaletteChange[];
  325. };
  326.  
  327. struct BigLineChanges {
  328.    UWORD ChangeCount;
  329.    struct BigPaletteChange PaletteChange[];
  330. };
  331.  
  332. struct BigPaletteChange {
  333.    UWORD Register;
  334.    UBYTE Alpha, Red, Blue, Green;
  335. };
  336.  
  337. PCHG ::= "PCHG" #{ (struct PCHGHeader) (LINEDATA | COMPLINEDATA) }
  338.  
  339.  
  340. COMPLINEDATA ::= { TREE COMPDATA }
  341. TREE ::= { UWORD* }
  342. COMPDATA ::= { ULONG* }
  343.  
  344. COMPDATA, when unpacked, gives a LINEDATA.
  345.  
  346.  
  347. LINEDATA ::= { LINEMASK ((struct SmallLineChanges)* | (struct BigLineChanges)*) }
  348. LINEMASK ::= { ULONG* }
  349.  
  350. The following relations hold:
  351.  
  352. #LINEDATA == PCHGHeader.OriginalSize
  353. #LINEMASK == ((PCHGHeader.LineCount+31)/32)*4
  354. #TREE  == PCHGHeader.TreeSize
  355.  
  356. PCHG is a property chunk. For the meaning of the above grammar, see the IFF
  357. documentation (the grammar does not give account for all the aspects of PCHG
  358. though). Note that my use of the [] notation for variable length arrays is
  359. not a C feature, but a shorthand.
  360.  
  361.  
  362. Please comment as soon as possible this document. You can use mail or
  363. e_mail as you prefer.
  364.  
  365.     Sebastiano Vigna
  366.     Via Valparaiso 18
  367.     I-20144 Milano MI
  368.  
  369.     BIX: svigna
  370.     UUCP:...{uunet|piramid|rutgers}!cbmvax!cbmehq!cbmita!sebamiga!seba
  371.  
  372. ==========================
  373.